트리냐 벡터냐 그것이 문제로다.
트리는 검색을 위해 적게 돌아다닌다. 대부분 O(logN) 정도다. 자료구조 크기가 크다. 검색을 위해 돌아다닌다. 캐시의 효용을 누리가 어렵다. 벡터(배열)은 순차 처리를 한다. 캐시의 효용을 누리기 좋다. SIMD나 멀티쓰레드로 처리(로캘리티 집중하면서 거짓공유는 회피할 수 있을 때)할 경우 한 방에 많이 처리하면서 캐시힛트를 최대로 누릴 수 있다.
100개의 키를 찾는다고 할 때, 100개의 키는 2^7 안에 들어가니까 밸런스드 트리에서 최악에도 6번 정도면 찾는다. 배열이라면 최악에 100 바퀴 돌아야 한다.
해싱 비용 때문에 문자열을 날로 찾아야 한다고 가정했을 때, 아호코라식은 기본 알고리즘상 1글자마다 트리 분기가 일어난다. 아마도 최적화된 알고리즘들은 그리 처리하진 않을 것이다. 벡터로 처리하면 avx2 등으로 한 방에 펑펑 처리하며 캐시의 혜택을 누릴 수 있다. 하지만 전수 뺑뺑이의 함정은 있다. 결국 사용 도메인 특성에 따라 배열이 이기는 쪽도 있는데, 뭘 써야 할지는 통찰이나 짬밥에 결정된다. 적절한 레퍼런스 테스트 셋을 구해서 돌릴 수 있으면 좋겠지만.. 그게 실은 거의 논문용, 제네릭 커버리지를 갖는 테스트 셋이지 바이어스가 심한 특정 도메인의 상업용이 아니다. 더더군다나 한글 레퍼런스 테스트 셋이라면..